package _0056_Merge_Intervals;

import _0000_study._common.Output;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public int[][] merge(int[][] a) {
        // 1、首先对列表中的元素基于第一个元素从小到大排序；
        Arrays.sort(a, (x, y) -> x[0] - y[0]);

        // 2、区间求并集
        List<List<Integer>> ans = new ArrayList<>();
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.length; i++)
            if (a[i][0] > r) {
                ans.add(Arrays.asList(l, r));
                l = a[i][0]; r = a[i][1];
            } else r = Math.max(r, a[i][1]);

        // 整理结果
        int[][] res = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            for (int j = 0; j < ans.get(0).size(); j++)
                res[i][j] = ans.get(i).get(j);
        }
        return res;
    }

    public static void main(String[] args) {

        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        Output.OutputBasicArray2D((new Solution()).merge(intervals));
    }
}
